【题解】 [SDOI2010]古代猪文 组合数学 luoguP2480 | Qiuly's blog!

【题解】 [SDOI2010]古代猪文 组合数学 luoguP2480

Posted on | In | Comments:

题目传送门：传送门戳我

很显然题目需要我们求出 $G^{\sum_{d|n}C_n^d} \ mod\ P$ ( $P=999911659$ ) 。我们知道费马小定理有一个推论：$a^{x}\equiv a^{x \ mod\ (P-1)} \ (mod \ P)$ (需要满足 $P$ 是质数) ，题目中的 $P$ 正好是质数，那么我们可以将上式变换一下：

现在我们需要快速求出 $\sum_{d|n}C_n^d \ mod\ (P-1)$ ，看样子可以 $lucas$ 直接求组合数，但是模数太大了不方便。分解质因数后发现 $999911658=2\times 3\times 4679\times 35617$ ，对四个模数求出其对应的答案，然后因为四个模数互质，最后 $crt$ 合并答案即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mod 999911658

ll n,g,fac[35617+7];
ll m[5]={0,2,3,4679,35617},a[5];

namespace math {
    inline ll pow(ll x,ll y,ll p) {
        ll res=1;
        for(;y;y>>=1,x=1ll*x*x%p) if(y&1) res=1ll*res*x%p; 
        return res;
    }
    inline ll C(ll n,ll m,ll p) {
        if(m>n)return 0;
        return ((fac[n]*pow(fac[m],p-2,p))%p*pow(fac[n-m],p-2,p)%p)%p;
    }
    inline ll lucas(ll n,ll m,ll p) {
        if(!m) return 1;
        return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
    }
    inline ll exgcd(ll a,ll b,ll&x,ll&y) {
        if(!b) {x=1,y=0;return a;}
        ll gcd=exgcd(b,a%b,x,y),tmp=x;
        x=y,y=tmp-(a/b)*y;return gcd;
    }
    inline ll CRT(ll*m,ll*a,int n) {
        ll res=0,lcm=1;
        for(ll i=1;i<=n;++i) lcm=lcm*m[i];
        for(ll i=1;i<=n;++i) {
            ll num=lcm/m[i],x,y,gcd=exgcd(num,m[i],x,y);
            x=(x%m[i]+m[i])%m[i];
            res=(res+a[i]*x*num)%lcm;
        }return res;
    }
}using namespace math;

int main() {
    scanf("%lld%lld",&n,&g);
    if(!(g%(mod+1))) {puts("0");return 0;}
    fac[0]=1;
    for(int i=1;i<=35617;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for(int k=1;k<=4;++k) {
        ll p=m[k],res=0;
        for(ll i=1;i*i<=n;++i) if(!(n%i)) {
            ll x=i,y=n/i;if(x==y) y=0;
            res=(res+lucas(n,x,p)%p)%p;
            if(y) res=(res+lucas(n,y,p)%p)%p;
        }
        a[k]=res;
    }
    ll ans=CRT(m,a,4);
    printf("%lld\n",pow(g,ans,mod+1));
    return 0;
}

本文标题:【题解】 [SDOI2010]古代猪文 组合数学 luoguP2480

文章作者:Qiuly

发布时间:2019年05月17日 - 00:00

最后更新:2019年05月17日 - 10:15

原始链接:http://qiulyblog.github.io/2019/05/17/[题解]luoguP2480/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。